﻿// 1006train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <vector>

using namespace std;

/*
 如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"
{0,0,2},
{1,3,4},
{6,6,4}
明文"0 3",密文"0 1 1 1"

输入描述
第一行输入1个正整数N，代表明文的长度(1 <= N <= 9)
第二行输入N个明文数字组成的序列Data[i](整数，0 <= Data[i] <= 9)
第三行输入1个正整数M，(1 <= M <= 9)
接下来输入一个M*M的矩阵代表密码本Book[i][i]

输出描述
如明文 第i位Data[i]对应密码本单元格为Book[i][j]，
则明文第i位对应的密文为X Y，X和Y之间用空格隔开
如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"

输入
2
0 3
3
0 0 2
1 3 4
6 6 4
输出
0 1 1 1

输入
4
0 0 2 4
4
0 0 2 4
1 3 4 6
3 4 1 5
6 6 6 5
输出
0 0 0 1 0 2 0 3
 */
class Solution01
{
public:
    struct Node
    {
        int row, col;
        Node() = default;
        Node(int row, int col) :row(row), col(col) {};
    };

    void backTrack(
        vector<int>& target_v, 
        vector<vector<int>>& grid,
        vector<vector<bool>>&checked,
        Node&curr_node
    )
    {
        int target_v_size = target_v.size();
        if (target_i==target_v_size)
        {
            is_find = true;
            result.push_back(track_v);
            return;
        }
        for (auto&dir_v:DirectionGrid)
        {
            int row = curr_node.row + dir_v[0];
            int col = curr_node.col + dir_v[1];

            bool is_row = row >= 0 && row < g_size_;
            bool is_col = col >= 0 && col < g_size_;

            if (!is_row || !is_col) continue;

            bool is_visited = checked[row][col];
            bool is_available = grid[row][col] == target_v[target_i];

            if (!is_visited && is_available)
            {
                Node next_node(row, col);
                target_i++;
                checked[row][col] = true;
                track_v.push_back(next_node);
                backTrack(target_v, grid, checked, next_node);
                target_i--;
                checked[row][col] = false;
                track_v.pop_back();
	            //
            }


	        //for---
        }
        

	    //---
    }
    Solution01(vector<int>&target_v, vector<vector<int>>&grid, int g_size)
    {
        g_size_ = g_size;
        vector<vector<bool>>checked(g_size_, vector<bool>(g_size_));

        for (int r=0; r<g_size_; r++)
        {
            for (int c=0; c<g_size_; c++)
            {
                if (target_v[target_i]==grid[r][c])
                {
                    Node node(r, c);
                    target_i++;
                    checked[r][c] = true;
                    track_v.push_back(node);
                    backTrack(target_v, grid, checked, node);
                    target_i--;
                    checked[r][c] = false;
                    track_v.pop_back();
	                //
                }

	            //for---
            }

	        //for---
        }

        //无法匹配，返回"error"
        if (!is_find)
        {
            cout << "error";
            return;
        }

        sort(result.begin(), result.end(), [](vector<Node>&vec_1, vector<Node>& vec_2)
            {
                int v_size = vec_1.size();
		        for (int i=0; i<v_size; i++)
		        {
                    bool is_row = vec_1[i].row == vec_2[i].row;
                    bool is_col = vec_1[i].col == vec_2[i].col;

                    if (is_row && is_col) continue;

                    int row_1 = vec_1[i].row;
                    int row_2 = vec_2[i].row;
                    if (!is_row) return row_1<row_2;

                    int col_1 = vec_1[i].col;
                    int col_2 = vec_2[i].col;
                    if (!is_col) return col_1 < col_2;
		            //for---
		        }

            });

        for (auto&node: result[0])
        {
            cout << node.row << ' ' << node.col << ' ';
        }

	    //Solu
    }
private:
    bool is_find = false;
    int target_i = 0, g_size_ = 0;
    vector<Node>track_v;
    vector<vector<Node>>result;
    vector<vector<int>>DirectionGrid = {
		{-1,0},{1,0},{0,-1},{0,1}
    };
};


string solve(string s, string t) {
    // write code here
    int s_size = s.size();
    int t_size = t.size();

    string result;
    int carry = 0;

    int s_index = s_size - 1;
    int t_index = t_size - 1;

    while (s_index >= 0 || t_index >= 0 || carry > 0)
    {
        int sum = carry;
        carry = 0; //清空上一轮进位
        if (s_index >= 0)
        {
            sum += s[s_index] - '0';
            s_index--;
        }
        if (t_index >= 0)
        {
            sum += t[t_index] - '0';
            t_index--;
        }
        if (sum >= 10)
        {
            carry = 1;
        }
        result += to_string(sum % 10);
        //while---
    }
    reverse(result.begin(), result.end());
    return result;
}



class Solution02 {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @return int整型vector<vector<>>
     */
    void backTrack(vector<int>& num, vector<bool>& checked)
    {
        if (track_v.size() == num.size())
        {
            result.push_back(track_v);
            return;
        }
        int v_size = num.size();
        for (int i = 0; i < v_size; i++)
        {
            //剪枝
            if (checked[i]) continue;
            if (i > 0 && num[i] == num[i - 1] && !checked[i - 1])
            {
                continue;
            }

            track_v.push_back(num[i]);
            checked[i] = true;
            backTrack(num, checked);
            checked[i] = false;
            track_v.pop_back();
        }
    }
    vector<vector<int> > permuteUnique(vector<int>& num) {
        // write code here
        sort(num.begin(), num.end());
        int v_size = num.size();
        vector<bool>checked(v_size, false);
        backTrack(num, checked);
        return result;
        //
    }
private:
    vector<int>track_v;
    vector<vector<int>>result;
};


class Solution03 {
public:
    void backTrack(vector<int>& nums, vector<bool>& checked, int start)
    {
        result.push_back(track_v);

        int v_size = nums.size();
        for (int i = start; i < v_size; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1] && !checked[i - 1]) continue;
            checked[i] = true;
        	track_v.push_back(nums[i]);
            backTrack(nums, checked, i + 1);
            checked[i] = false;
            track_v.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int v_size = nums.size();
        vector<bool>checked(v_size);
        backTrack(nums, checked, 0);
        return result;
    }
private:
    vector<int>track_v;
    vector<vector<int>>result;
};

/*
构造数列，第一个数为n，后面的数不大于前一个的一半，
数列奇偶相间或者全为奇数或者全为偶数，数列的元素都是正整数，能构造多少数列。

输入描述
输入一个n

输出描述
输出可以构造的序列个数
 */

class Solution04
{
public:
    int computeSame(int num)
    {
	    //奇偶相同
        vector<int>dynamic_v(num + 1, 1);
        int start = 1;
        if (num % 2 == 0)
            start = 2;

        for (int i = start; i<=num; i+=2)
        {
            for (int prev=start; prev*2<=i; prev+=2)
            {
                dynamic_v[i] += dynamic_v[prev];
            }
        }
        return dynamic_v[num];
        //compute
    }
    int computeDiff(int num)
    {
        //奇偶相间
        vector<int>dynamic_v(num + 1, 1);

        for (int i=1; i<=num; i++)
        {
            int start = 1;
            if (i % 2 == 1)
                start = 2;
            for (int prev=start; prev*2<=i; prev+=2)
            {
                dynamic_v[i] += dynamic_v[prev];
            }

        }
        return dynamic_v[num];
        //compute
    }
    Solution04(int num)
    {
	    //1,2,7 后一个数大于等于前一个数的两倍
        int same = computeSame(num);
        int diff = computeDiff(num);

        //记得一定要减1，两个集合都重复算了{num}
        cout << same + diff - 1;

        //Solution04
    }
};

string LCS(string s1, string s2) {
    // write code here

    int size_1 = s1.size(), size_2 = s2.size();
    int row_size = size_1 + 1, col_size = size_2 + 1;
    vector<vector<string>>dynamic_v(row_size, vector<string>(col_size));

    int max_length = 0;
    string result;
    for (int r = 1; r < row_size; r++)
    {
        for (int c = 1; c < col_size; c++)
        {
            if (s1[r - 1] != s2[c - 1])
            {
                int prev_r = dynamic_v[r - 1][c].size();
                int prev_c = dynamic_v[r][c - 1].size();

                dynamic_v[r][c] = dynamic_v[r - 1][c];
                if (prev_c > prev_r)
                    dynamic_v[r][c] = dynamic_v[r][c - 1];

            }
            else {
                string curr_str = dynamic_v[r - 1][c - 1] + s1[r - 1];
                dynamic_v[r][c] = curr_str;
                int curr_size = curr_str.size();
                if (curr_size > max_length)
                {
                    result = curr_str;
                    max_length = curr_size;
                }

            }

        }
    }
    return result;
    //---
}
int main()
{
	{
        //"1A2C3D4B56","B1D23A456A"
        string s1 = "1A2C3D4B56", s2 = "B1D23A456A";

        LCS(s1, s2);
        return 0;
	}
	{
        //int num = 4;
        int num;
        cin >> num;
        Solution04 solu(num);
        return 0;
	}
	{
        vector<int>nums = { 1,2,2 };
        Solution03 solu;
        solu.subsetsWithDup(nums);

        return 0;
	}
	{
        //[1,1,2]
        vector<int>num = { 1,1,2 };
        Solution02 solu;
        solu.permuteUnique(num);

        return 0;
	}
	{
        //"1","99"
        string s = "1", t = "99";
        cout << solve(s, t);

        return 0;
	}
    int t_size;
    cin >> t_size;
    vector<int>target_vec(t_size);
    for (int i=0; i<t_size; i++)
    {
        cin >> target_vec[i];
    }
    int g_size;
    cin >> g_size;
    vector<vector<int>>grid(g_size,vector<int>(g_size));
    for (int r=0; r<g_size; r++)
    {
	    for (int c=0; c<g_size; c++)
	    {
            cin >> grid[r][c];
	    }
    }
    Solution01 solu(target_vec, grid, g_size);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
